정점 개, 간선 개의 단순 양방향 그래프가 주어진다.
각 정점에는 열쇠가 하나씩 있는데, 번 정점의 열쇠의 종류는 이다.
각 간선을 지나기 위해서는 열쇠가 있어야 하는데, 번째 간선을 지나기 위해 필요한 열쇠의 종류는 이다. 번 정점에서 이동을 시작할 때, 정점들을 돌아다니며 얻을 수 있는 열쇠를 얻고, 자신이 갖고 있는 열쇠를 이용하여 이동이 가능한 간선을 따라 이동할 수 있다.
이와 같이 번 정점에서 시작하였을 때 도달가능한 정점들의 개수가 최소가 되는 정점 들의 집합을 구하여라.
각 정점에서 시작하여, 이 정점에서 도달할 수 있는 모든 정점들을 구하기 위하여 다음과 같은 BFS 알고리즘을 생각하자.
그래프 탐색을 하며 "지금까지 방문한 정점들의 열쇠 의 집합"과, "지금까지 방문한 정점들과 인접한 간선들 중 아직 열쇠를 발견하지 못한 간선들의 집합"을 종류별로 나누어 배열으로 관리하자.
만약 새로운 정점 를 방문하였는데, 가 지금까지는 본 적 없는 종류의 열쇠라면, 이 열쇠를 이용하여 이전에는 사용하지 못했던, 를 만족하는 간선 들을 queue에 삽입해주면 된다.
새로운 간선 를 발견하였는데, 가 이미 발견한 종류의 열쇠라면 바로 queue에 삽입해주면 되고, 아니면 아직 열쇠를 발견하지 못한 간선들의 리스트에 추가해주면 된다.
위 알고리즘을 통하여 각 시작점에 대하여 의 시간에 BFS를 할 수 있으니, 전체 의 시간에 문제를 해결할 수 있다.
Checkpoint
각 정점에서 시작하여, 이 정점에서 도달할 수 있는 모든 정점들을 구하기 위하여 다음과 같은 BFS 알고리즘을 생각하자.
그래프 탐색을 하며 "지금까지 방문한 정점들의 열쇠 의 집합"과, "지금까지 방문한 정점들과 인접한 간선들 중 아직 열쇠를 발견하지 못한 간선들의 집합"을 종류별로 나누어 배열으로 관리하자.
만약 새로운 정점 를 방문하였는데, 가 지금까지는 본 적 없는 종류의 열쇠라면, 이 열쇠를 이용하여 이전에는 사용하지 못했던, 를 만족하는 간선 들을 queue에 삽입해주면 된다.
새로운 간선 를 발견하였는데, 가 이미 발견한 종류의 열쇠라면 바로 queue에 삽입해주면 되고, 아니면 아직 열쇠를 발견하지 못한 간선들의 리스트에 추가해주면 된다.
위 알고리즘을 통하여 각 시작점에 대하여 의 시간에 BFS를 할 수 있으니, 전체 의 시간에 문제를 해결할 수 있다.
문제를 해결하기 전에, 이 문제의 상황은 일반적인 방향그래프의 SCC의 상황과 매우 비슷하다.
정점 에서 시작하여 도달 가능한 정점들의 집합을 라 할 때, 와 가 같은 SCC에 속한다는 것은 라는 것과 필요충분이며, SCC는 에 대한 equivalence class라고 생각할 수 있다.
또한, 방향 간선 가 존재한다면 가 성립하고, 라면 가 성립한다.
번 정점에서 시작하였을 때 도달가능한 정점들의 개수가 최소가 되는 정점 들의 집합을 구해야 하는 이 문제의 상황을 SCC의 상황으로 생각해보면, 결국 condensation graph에서 outdegree가 없는 SCC들을 모두 구해야 하는 상황과 일치한다.
condensation graph에서 outdegree가 없는 SCC에 속하는 정점 에 대해서는 인 다른 정점 에 대해 라는 것을 알 수 있다.
Observation 1
방향그래프의 SCC에는 다음과 같은 성질들이 성립한다.
정점 에서 시작하여 도달 가능한 정점들의 집합을 라 하자.
와 가 같은 SCC에 속한다는 것은 라는 것과 필요충분이며, SCC는 에 대한 equivalence class라고 생각할 수 있다.
방향 간선 가 존재한다면 가 성립한다.
라면, 가 성립한다.
condensation graph에서 outdegree가 없는 SCC에 속하는 정점 에 대해서는 인 다른 정점 에 대해 가 성립한다.
위 Observation 1의 성질은 SCC에서 성립하는 성질이지만, 이 문제에서도 성립하며 풀이의 결정적인 관찰을 제공한다.
따라서, 이 문제의 조건과 상황은 다르더라도 이와 같이 각 정점에서 번 정점에서 시작하였을 때 도달가능한 정점들의 개수가 최소가 되는 정점 들의 집합을 구해야 하는 문제에서 이 문제의 풀이를 적용할 수 있다.
번 정점에서 시작하였을 때 도달가능한 정점들의 집합을 라 하자.
간선 에 대하여 만약 의 정점들 중 열쇠 를 얻을 수 있는 정점이 포함되어 있다면, 에서 시작하여 로 이동할 수 있으며, 따라서 가 성립한다.
Observation 2
번 정점에서 시작하였을 때 도달가능한 정점들의 집합을 라 하자.
간선 에 대하여 만약 의 정점들 중 열쇠 를 얻을 수 있는 정점이 포함되어 있다면, 에서 시작하여 로 이동할 수 있으며, 따라서 가 성립한다.
간선 에 대하여 이면, Observation 2에 의해 가 성립한다.
각 에 대하여 이와 같이 확실히 라는 것을 아는 정점 에 대하여 로 간선을 하나씩 이어 주면, 완성된 그래프에서 각 정점의 outdegree는 아니면 으로, functional graph나 트리들의 집합이 된다.
이 때, functional graph의 루트에 해당하는 사이클 에 대해 다음이 성립한다.
즉, functional graph의 루트에 해당하는 사이클 에 해당하는 모든 정점들의 가 같으니 이들을 하나의 정점으로 묶어서 취급할 수 있다.
(이는 방향 그래프에서 정점들을 가 같은 정점들을 하나의 SCC로 묶는다고 생각해도 된다.)
이후, 묶인 새로운 정점들의 열쇠 집합과 간선 집합을 하나로 묶어준 후, 다시 간선 에 대하여 인 를 찾아 로 간선을 새롭게 이어주면 된다.
위 과정을 반복하다 보면, 완성된 그래프는 더이상 functional graph가 남아 있지 않고, 여러 트리들의 집합이 남는다.
의 크기가 최소가 되는 정점 는 Observation 1과 같이 인 다른 정점 에 대해 가 성립해야 한다.
트리의 루트에 속하는 정점들은 더 이상 밖으로 나가는 간선을 찾을 수 없다는 의미이니, 집합 밖으로 이동할 수 없고, 따라서 답으로 가능한 정점들은 오직 루트에 속한 정점들이다.
전체 알고리즘은 위와 같이 정점들의 집합을 관리하며, 각 집합에서 밖으로 나갈 수 있는 한 정점 를 이용하여 functional graph를 만들고, 루트에 해당하는 사이클을 묶어서 한 집합으로 만든 후 새로운 를 구해주어야 한다.
이를 효율적으로 관리하기 위하여 Union Find와 각 정점의 열쇠 집합과 나가는 간선들의 집합을 관리하기 위하여 Set과 Small to Large를 이용하면 된다.
전체 시간복잡도는 Set에서 Small to Large를 해야 하니, 이 된다.
CheckPoint
간선 에 대하여 이면, Observation 2에 의해 가 성립한다.
각 에 대하여 이와 같이 확실히 라는 것을 아는 정점 에 대하여 로 간선을 하나씩 이어 주면, 완성된 그래프에서 각 정점의 outdegree는 아니면 으로, functional graph나 트리들의 집합이 된다.
이 때, functional graph의 루트에 해당하는 사이클 에 해당하는 모든 정점들의 가 같으니 이들을 하나의 정점으로 묶어서 취급할 수 있다.
이후, 묶인 새로운 정점들의 열쇠 집합과 간선 집합을 하나로 묶어준 후, 다시 간선 에 대하여 인 를 찾아 로 간선을 새롭게 이어주면 된다.
위 과정을 반복하다 보면, 완성된 그래프는 더이상 functional graph가 남아 있지 않고, 여러 트리들의 집합이 남는다.
트리의 루트에 속하는 정점들은 더 이상 밖으로 나가는 간선을 찾을 수 없다는 의미이니, 집합 밖으로 이동할 수 없고, 따라서 답으로 가능한 정점들은 오직 루트에 속한 정점들이다.
이를 효율적으로 관리하기 위하여 Union Find와 각 정점의 열쇠 집합과 나가는 간선들의 집합을 관리하기 위하여 Set과 Small to Large를 이용하면 된다.
전체 시간복잡도는 Set에서 Small to Large를 해야 하니, 이 된다.